import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 面试题 08.08. 有重复字符串的排列组合
 * https://leetcode-cn.com/problems/permutation-ii-lcci/
 */
public class Solutions_mianshi_08_08 {
    public static void main(String[] args) {
        String str = "qqe";  // output: {"eqq", "qeq", "qqe"}
        String[] result = permutation(str);
        System.out.println(Arrays.toString(result));
    }

    private static List<String> list = null;
    private static boolean[] visited = null;
    public static String[] permutation(String S) {
        char[] arr = S.toCharArray();
        // 排序，使得相同的字符相邻
        Arrays.sort(arr);
        char[] res = new char[arr.length];
        // visited[2] = true，表示 arr[2] 字符已经添加到了 res 中
        visited = new boolean[arr.length];
        list = new ArrayList<>();
        backtrack(arr, res, 0);
        return list.toArray(new String[list.size()]);
    }

    public static void backtrack(char[] arr, char[] res, int index) {
        if (index == arr.length) {
            list.add(new String(res));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) {
                // 访问过的字符，不添加
                continue;
            }
            if (i > 0 && arr[i] == arr[i - 1] && !visited[i - 1]) {
                // 保证不会添加重复的排列组合
                continue;
            }
            // 添加字符，标记状态
            res[index] = arr[i];
            visited[i] = true;
            backtrack(arr, res, index + 1);
            // 还原标记
            visited[i] = false;
        }
    }
}
